Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model
Yipeng SHI, Jie LIU, Jinyuan ZU, Tao ZHANG, Guoqun ZHANG
Journal of Computer Applications    2023, 43 (5): 1504-1510.   DOI: 10.11772/j.issn.1001-9081.2022040496
Abstract236)   HTML4)    PDF (503KB)(85)       Save

Applying the compact constraint calculation method of S-box based on Mixed Integer Linear Programming (MILP) model can solve the low efficiency of differential path search of SPONGENT in differential cryptanalysis. To find the best description of S box, a compactness verification algorithm was proposed to verify the inequality constraints in S-box from the perspective of the necessity of the existence of constraints. Firstly, the MILP model was introduced to analyze the inequality constraints of SPONGENT S-box, and the constraint composed of 23 inequalities was obtained. Then, an index for evaluating the existence necessity of constraint inequality was proposed, and a compactness verification algorithm for verifying the compactness of group of constraint inequalities was proposed based on this index. Finally, the compactness of the obtained SPONGENT S-box constraint was verified by using the proposed algorithm. Calculation analysis show that the 23 inequalities have a unique impossible difference mode that can be excluded, that is, each inequality has the necessity of existence. Furthermore, for the same case, the number of inequalities was reduced by 20% compared to that screened by using the greedy algorithm principle. Therefore, the obtained inequality constraint of S-box in SPONGENT is compact, and the proposed compactness verification algorithm outperforms the greedy algorithm.

Table and Figures | Reference | Related Articles | Metrics